package jm.algorithm.sort;

/**
 * @Description 优化版计数排序
 * @date 2022/5/8 15:58
 */
public class CountingSortPro extends Sort<Integer> {
    @Override
    protected void sort() {
        // 获取数组最大值
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
            if (arr[i] < min){
                min = arr[i];
            }
        }

        // 开辟内存空间
        int[] counts = new int[max - min + 1];

        // 统计次数
        for (Integer integer : arr) {
            counts[integer - min]++;
        }

        // 统计累加的次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 倒序遍历然后将值放到合适位置
        int[] newArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            // 将当前值根据在counts中的索引计算出新的位置。
            // 先将值减一，在计算出当前值对应的索引
            int index = --counts[arr[i] - min];
            // 放到新序列中。
            newArr[index] = arr[i];
        }

        // 覆盖序列
        for (int i = 0; i < newArr.length; i++) {
            arr[i] = newArr[i];
        }
    }
}
